package binarysearchTree;

public class BinarySearchTree {
    static class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public boolean insert(int val) {
        TreeNode newNode = new TreeNode(val);
        if(root==null) {
            root = newNode;
            return true;
        }
        TreeNode prevNode = null;
        TreeNode curNode = root;
        while (curNode!=null) {
            prevNode = curNode;
            if(val>curNode.val) {
                curNode = curNode.right;
            } else if (val<curNode.val) {
                curNode = curNode.left;
            }
        }
        if(val > prevNode.val) {
            prevNode.right = newNode;
        } else {
            prevNode.left = newNode;
        }
        return false;
    }

    public boolean search(int key) {
        TreeNode cur = root;
        while (cur!=null) {
            if(cur.val==key) {
                return true;
            } else if (cur.val<key) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return false;
    }

    public boolean remove(int val) {
        if(!search(val)) {
            System.out.println("该值不存在,无法删除");
            return false;
        }
        if(root.val==val&&root.left==null) {
            root = root.right;
            if(!search(val)) {
                System.out.println("删除成功");
                return true;
            }else {
                System.out.println("删除失败");
                return false;
            }
        }
        if(root.val==val&&root.right==null) {
            root = root.right;
            if(!search(val)) {
                System.out.println("删除成功");
                return true;
            }else {
                System.out.println("删除失败");
                return false;
            }
        }
        if (root.val==val) {
            TreeNode tmpNode = root.right;
            root = root.left;
            TreeNode node = root;
            while (node.right!=null) {
                node = node.right;
            }
            node.right = tmpNode;
            if(!search(val)) {
                System.out.println("删除成功");
                return true;
            }else {
                System.out.println("删除失败");
                return false;
            }
        }
        TreeNode curNode = root;
        TreeNode prevNode = null;
        while (curNode!=null) {
            if(val>curNode.val) {
                prevNode = curNode;
                curNode = curNode.right;
            } else if (val<curNode.val) {
                prevNode = curNode;
                curNode = curNode.left;
            } else {
                removeNode(curNode,prevNode);
                if(!search(val)) {
                    System.out.println("删除成功");
                }else {
                    System.out.println("删除失败");
                }
                return true;
            }
        }


        return true;
    }

    private void removeNode(TreeNode curNode, TreeNode prevNode) {
        if(curNode.val>prevNode.val) {
            if(curNode.left==null&&curNode.right==null) {
                prevNode.right = null;
            }
            if(curNode.left==null&&curNode.right!=null) {
                prevNode.right = curNode.right;
            }
            if(curNode.left!=null&&curNode.right==null) {
                prevNode.right = curNode.left;
            }
            if(curNode.left!=null&&curNode.right!=null) {
                prevNode.right = curNode.left;
                TreeNode tmpNode = curNode.left;
                while (tmpNode.right!=null) {
                    tmpNode = tmpNode.right;
                }
                tmpNode.right = curNode.right;
            }

        } else if (curNode.val<prevNode.val) {
            if(curNode.left==null&&curNode.right==null) {
                prevNode.left = null;
            }
            if(curNode.left!=null&&curNode.right==null) {
                prevNode.left = curNode.left;
            }
            if(curNode.left==null&&curNode.right!=null) {
                prevNode.left = curNode.right;
            }
            if(curNode.left!=null&&curNode.right!=null) {
                prevNode.left = curNode.left;
                TreeNode tmpNode = curNode.left;
                while (tmpNode.right!=null) {
                    tmpNode = tmpNode.right;
                }
                tmpNode.right = curNode.right;
            }
        }


    }
}
